package study;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class AsteroidCollision {
    public static int[] asteroidCollision(int[] input) {
        if (input == null || input.length == 0) {
            return new int[]{};
        }
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < input.length; i++) {
            int exist = 1;
            while (exist > 0 && input[i] < 0 && !stack.isEmpty() && stack.peek() > 0) {
                if (stack.peek() >= -input[i]) {
                    exist = 0;
                }
                if (stack.peek() <= -input[i]) {
                    stack.pop();
                } else {
                    break;
                }
            }
            if (exist > 0) {
                stack.push(input[i]);
            }
        }
        int[] ret = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            ret[i] = stack.pop();
        }
        return ret;
    }

    // 对拍
    public static int[] asteroidCollision2(int[] input) {
        if (input == null || input.length == 0) {
            return new int[]{};
        }
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < input.length; i++) {
            if (i == 0) {
                stack.push(input[i]);
            } else {
                if (!stack.isEmpty() && stack.peek() > 0 && input[i] < 0) {
                    for (int j = stack.size(); j > 0; j--) {
                        if (stack.peek() == -input[i]) {
                            stack.pop();
                            break;
                        }
                        if (stack.peek() > -input[i]) {
                            break;
                        }
                        if (stack.peek() < -input[i]) {
                            stack.pop();
                        }
                    }
                } else {
                    stack.push(input[i]);
                }
            }
        }

        int[] ret = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            ret[i] = stack.pop();
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] input = {5, 10, -5, -10};
        int[] ret1 = asteroidCollision(input);
        int[] ret2 = asteroidCollision2(input);
        System.out.println(Arrays.toString(ret1));
        System.out.println(Arrays.toString(ret2));
    }
}
